package leetcode12;

import java.util.LinkedList;

/**
 * 739. 每日温度
 */
public class test68 {
    /**
     * 单调栈 右到左
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures1(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        LinkedList<Integer> stack = new LinkedList<>();
        for(int i = n - 1;i >= 0;i--){
            int t = temperatures[i];
            while(!stack.isEmpty() && temperatures[stack.peek()] <= t){
                stack.pop();
            }
            if(!stack.isEmpty()){
                res[i] = stack.peek() - i;
            }
            stack.push(i);
        }
        return res;
    }

    /**
     * 单调栈 左到右
     * @param temperatures
     * @return
     */

    public int[] dailyTemperatures2(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        LinkedList<Integer> stack = new LinkedList<>();
        for(int i = 0;i < n;i++){
            int t = temperatures[i];
            while(!stack.isEmpty() && t > temperatures[stack.peek()]){
                int p = stack.pop();
                res[p] = i - p;
            }
            stack.push(i);
        }
        return res;
    }
}
